package com.gitee.maojian.hash;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * BM51 数组中出现次数超过一半的数字
 * 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
 *
 * 数据范围：n \le 50000n≤50000，数组中元素的值 0 \le val \le 100000≤val≤10000
 * 要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)
 * 输入描述：
 * 保证数组输入非空，且保证有解
 *
 */
public class Q_BM51 {

    /**
     * 排序取中间值
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int[] array) {
        Arrays.sort(array);
        return array[array.length / 2];
    }

    /**
     * 候选法
     * 两两不相同的数据消去
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution01(int[] array) {
        int curNum = -1;
        int curCount = 0;
        for (int i = 0; i < array.length; i++) {
            if (curCount == 0) {
                curNum = array[i];
                curCount++;
            } else {
                if (curNum == array[i]) {
                    curCount++;
                } else {
                    curCount--;
                }
            }
        }
        return curNum;
    }

    /**
     * hash
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution02(int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i], map.getOrDefault(array[i], 0) + 1);
        }
        return map.entrySet().stream().filter(x -> x.getValue() > array.length / 2).findAny().get().getKey();
    }

    @Test
    public void test() {
        int[] array = new int[]{2, 2, 2, 2, 2, 1, 3, 4, 5};
        System.out.println(MoreThanHalfNum_Solution02(array));
    }
}
